class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 一、 枚举法：时间复杂度较高
        # n = len(nums)
        # if n == 1:
        #     if nums[0] == k:
        #         return 1
        #     else:
        #         return 0
        # count = 0
        # for right in range(n):
        #     sum = 0
        #     for left in range(right, -1, -1): 
        #         sum += nums[left]
        #         if sum == k:
        #             count += 1
        # return count

        # 二、前缀和 + 哈希表优化 pre[j-1] = pre[i] - k
        mp = {0: 1} 
        count = 0
        pre = 0
        for i in range(len(nums)):
            pre += nums[i]
            if pre - k in mp:
                count += mp[pre - k]
            mp[pre] = mp.get(pre, 0) + 1
        return count
